package com.lw.leetcode.dp.b;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * dp
 * 241. 为运算表达式设计优先级
 *
 * @Author liw
 * @Date 2021/8/28 18:35
 * @Version 1.0
 */
public class DiffWaysToCompute {

    public static void main(String[] args) {
        DiffWaysToCompute test = new DiffWaysToCompute();

        // [0, 2]
//        String str = "2-1-1";

        // [-34, -14, -10, -10, 10]
        String str = "2*3-4*5";

        List<Integer> list = test.diffWaysToCompute(str);
        System.out.println(list);

    }

    public List<Integer> diffWaysToCompute(String expression) {
        char[] chars = expression.toCharArray();
        List<Integer> valueList = new ArrayList<>();
        List<Character> opList = new ArrayList<>();
        int item = 0;
        for (char c : chars) {
            if (c == '+' || c == '-' || c == '*') {
                opList.add(c);
                valueList.add(item);
                item = 0;
            } else {
                item = item * 10 + c - 48;
            }
        }
        valueList.add(item);
        int length = valueList.size();
        Map<Integer, List<Integer>> map = new HashMap<>((length * length) << 1);
        for (int i = 0; i < length; i++) {
            List<Integer> list = new ArrayList<>();
            list.add(valueList.get(i));
            map.put(i * length + i, list);
        }

        for (int i = length - 2; i >= 0; i--) {
            for (int j = i + 1; j < length; j++) {
                List<Integer> list = new ArrayList<>();
                map.put(i * length + j, list);
                for (int k = i; k < j; k++) {
                    List<Integer> a = map.get(i * length + k);
                    List<Integer> b = map.get((k + 1) * length + j);
                    char ch = opList.get(k);
                    if (ch == '+') {
                        for (Integer av : a) {
                            for (Integer bv : b) {
                                list.add(av + bv);
                            }
                        }
                    } else if (ch == '-') {
                        for (Integer av : a) {
                            for (Integer bv : b) {
                                list.add(av - bv);
                            }
                        }
                    } else {
                        for (Integer av : a) {
                            for (Integer bv : b) {
                                list.add(av * bv);
                            }
                        }
                    }
                }
            }
        }
        return map.get(length - 1);
    }




}
